class Solution {
    public int[] smallestSufficientTeam(String[] req_skills, List<List<String>> people) {
       int m = req_skills.length,n = people.size();
       Map<String,Integer> map = new HashMap<>();
       for(int i=0;i<m;i++){
           map.put(req_skills[i],i);
       }

       List<Integer>[] dp = new List[1 << m];
       dp[0] = new ArrayList<>();
       for(int i=0;i<n;i++){
           List<String> curP = people.get(i);
           int curS = 0;
           for(String tmp:curP){
               curS |= 1 << map.get(tmp);
           }

           for(int j=0;j<dp.length;j++){
               if(dp[j] == null){
                   continue;
               }

               int curA = curS | j;
               if(dp[curA] == null || dp[j].size() + 1 < dp[curA].size()){
                   dp[curA] = new ArrayList<>(dp[j]);
                   dp[curA].add(i);
               }
           }
       }

       return dp[(1 << m) -1].stream().mapToInt(i->i).toArray();
    }
}

